/*  slfdkmul.cpp  by K.Tsuru  */
// function ID = 219    DRADIX, BRADIX
/*************************************************
SLong and SInteger classes
z = (huge x) * (huge y) for x.Size() >= y.Size()
It provides the Karatsuba's multiplication.
***************************************************/
#ifndef SN_H
#include "sn.h"
#endif
void SLong::KaratsubaHHMult(const SLong& x, const SLong& y, SLong& z){
    uint xfig = ceilpow2(x.Head()+1), yfig = ceilpow2(y.Head()+1), k, fms;
    fms = x.FFTMaxArraySize()/2;
    if( (xfig <= fms) && (yfig <= fms) ){
        z = x*y;
        return;
    }
    SLong p, q, t;

    p.CutDown(ENABLE);
    p = x;  q = y;
    p.CutDown(p.POP);
    p.CutDown(DISABLE);

    if( (xfig > fms) && (fms > yfig) ) yfig = fms;
    uint dN = xfig/yfig;    // number of division
#ifndef NDEBUG
assert(dN);     // |x| >= |y|
#endif
if(dN == 1){
        KHHMult(p, q, z);       return;
    }
//  divided p into dN parts a[dN].
    SLong* a = new SLong[dN];

    for(k = 0; k < dN ; k++){
        SLCutOut(a[k], p, k*yfig, yfig);
    }

    KHHMult(a[0], q, z);
    for(k = 1; k < dN ; k++){
        KHHMult(a[k], q, t);
        z += t.MultPowRdx(k*yfig);
    }
    delete [] a;
}